/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package hoja10;
import java.io.*;
/**
 *
 * @author RAUL
 */
public class Hoja10 {

    /**
     * @param args the command line arguments
     */
  
    private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        

                
   
                            
            
            
        System.out.println("Escribe la ciudad de origen");/*Starting city input*/
        String origen = in.readLine();
        
        System.out.println("Escribe la ciudad destino"); /*Final city input*/
        String destino = in.readLine();
        
       
        int i = 0;
        int j = 0;
        
        for(int ab=0; ab < 100; ab++)/*Changes the city name to citi number*/
            if(origen.compareToIgnoreCase(Cds[ab]) == 0)
                 i = (ab + 1);
            else{
                if(destino.compareToIgnoreCase(Cds[ab]) == 0)
                   j = (ab + 1);
            }
        
        
        String ruta = "";
      
        
        
        if (i > j){/*Switches starting and final city if starting city's index is greater than final's*/
            int temp = j;
            j = i;
            i = temp;
            int l = j;
            if (S[i][j] == j){
              System.out.println("La ruta mas corta es ir de: " + destino + " a " + origen );/*Prints the path when there is direct conection*/
               System.out.println("La distancia entre " + origen + " y " + destino + " es: " + A[i][j] + "km" );/*Prints the distance between the starting city and final city*/
                    System.out.println("Tiempo aproximado entre " + origen + " y " + destino + " a una velocidad promedio de 100km/h es: " +(A[i][j]/100) + " horas" );
        }else{
           
                    while ( S[i][l] != l){/*Checks in the adjacency matrix if the column index equals the the value in the box between i and l*/
                        while(S[l][S[i][l]] != S[i][l]){ /*checks l with the previous l to include all intermediate nodes  */
                            ruta += Cds[S[l][S[i][l]] - 1] + " --> "; /*Defines the path, using the index as city's index*/ 
                            l = S[l][S[i][l]]; 
                        }
                         ruta += Cds[S[i][l] - 1] + " --> ";                   
                         l = S[i][l]; /*Sets l as the value in the box between i and l  */
                    }
      
                    System.out.println("La ruta mas corta a tomar es la sigueinte: " + origen + " --> " + ruta + ""+ destino);/*Prints the shortest path*/
                    System.out.println("La distancia entre " + origen + " y " + destino + " es: " + A[i][j] + "km" );/*Prints the distance between the starting city and final city*/
                    System.out.println("Tiempo aproximado entre " + origen + " y " + destino + " a una velocidad promedio de 100km/h es: " +(A[i][j]/100) + " horas" );
              } 
        }
        else {/*This part of the code does the same thing than the previous one, but just when the starting city's index is greater than the final one*/
            
        int l = j;
        if (S[i][j] == j){
            System.out.println("La ruta mas corta es ir de: " + origen + " a " + destino );
             System.out.println("La distancia entre " + origen + " y " + destino + " es: " + A[i][j] + "km" );/*Prints the distance between the starting city and final city*/
             System.out.println("Tiempo aproximado entre " + origen + " y " + destino + " a una velocidad promedio de 100km/h es: " +(A[i][j]/100) + " horas" );
        } else{
           
            while ( S[i][l] != l){
                while(S[l][S[i][l]] != S[i][l]){
                            ruta = Cds[S[l][S[i][l]]-1] + " --> " + ruta +"";
                            l = S[l][S[i][l]];
                        }
                ruta = Cds[S[i][l] - 1] + " --> " + ruta + "";
                                          
                l = S[i][l];
               
                
            }
                               
         
      
                System.out.println("La ruta mas corta a tomar es la sigueinte: " + origen + " --> " + ruta + ""+ destino);
                System.out.println("La distancia entre " + origen + " y " + destino + " es: " + A[i][j] + "km" );
                 System.out.println("Tiempo aproximado entre " + origen + " y " + destino + " a una velocidad promedio de 100km/h es: " +(A[i][j]/100) + " horas" );
        }
          
        
        
        
        }   
        
    }
    
}

}
